from random import randint


class Map():
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.__map = []
        self.__signList = [(1, 1)]  # 起点
        self.__unsignList = []

    def mapData(self):
        self.__init_map()
        self.__create_map()

        return self.__map

    # 初始化地图
    def __init_map(self):
        for i in range(self.height):
            row = []
            if(i % 2 == 0):
                for j in range(self.width):
                    row.append(1)
            else:
                for j in range(self.width):
                    if(j % 2 == 0):
                        row.append(1)
                    else:
                        row.append(0)
            self.__map.append(row)

    def __create_map(self):
        while True:
            if(len(self.__signList)):
                self.__get_through()
            else:
                break

    # 从标记坐标列表中选取下标为0的元组作为起始点，
    # 一直往下打通墙，直到四周不存在未被标记的空间
    def __get_through(self, pos=""):
        #　若没有传入起始位置，取标记列表中的第一个坐标作为起始位置
        if(pos == ""):
            pos = self.__signList[0]

        # 获取起始坐标上下左右中未被标记的坐标作为目标位置列表
        target_pos_list = self.__get_around_pos(pos)

        # 如果目标位置列表不为空
        if(len(target_pos_list)):
            # 从目标位置列表中随机选取一个作为目标位置
            target_pos = self.__sign_pos(pos, target_pos_list)
            # 打通起始位置和目标位置之间的墙
            self.__break_wall(pos, target_pos)
            # 递归,将本次的目标位置作为下次的起始位置
            self.__get_through(target_pos)
        # 如果目标位置列表为空，说明路走到尽头
        # 将标记坐标列表的第一个坐标存放至已处理坐标列表
        # 结束本条路线
        else:
            self.__unsignList.append(self.__signList[0])
            del self.__signList[0]

    # 从坐标列表中随机取其中一个坐标,将该坐标存入标记列表中
    def __sign_pos(self, pos, target_pos_list):
        target_pos = target_pos_list[randint(0, len(target_pos_list) - 1)]
        self.__signList.append(target_pos)

        return target_pos

    # 将墙打通
    def __break_wall(self, pos, target_pos):
        if(target_pos[1] > pos[1]):
            x = pos[1] + 1
        elif(target_pos[1] < pos[1]):
            x = pos[1] - 1
        else:
            x = pos[1]

        if(target_pos[0] > pos[0]):
            y = pos[0] + 1
        elif(target_pos[0] < pos[0]):
            y = pos[0] - 1
        else:
            y = pos[0]

        self.__map[x][y] = 0

    # 获取指定位置四周未被标记空位
    def __get_around_pos(self, pos):
        around_pos = []
        data = []
        data.append(self.get_top_pos(pos, 2))
        data.append(self.get_right_pos(pos, 2))
        data.append(self.get_below_pos(pos, 2))
        data.append(self.get_left_pos(pos, 2))

        for item in data:
            if(item and item not in self.__signList and item not in self.__unsignList):
                around_pos.append(item)

        return around_pos

    # 获取指定坐标上方坐标
    def get_top_pos(self, pos, step):
        if(pos[1] - step >= 0):
            return (pos[0], pos[1] - step)
        return False

    # 获取指定坐标右方坐标
    def get_right_pos(self, pos, step):
        if(pos[0] + step < self.width):
            return (pos[0] + step, pos[1])
        return False

    # 获取指定坐标下方坐标
    def get_below_pos(self, pos, step):
        if(pos[1] + step < self.height):
            return (pos[0], pos[1] + step)
        return False

    # 获取指定坐标左方坐标
    def get_left_pos(self, pos, step):
        if(pos[0] - step >= 0):
            return (pos[0] - step, pos[1])
        return False

if __name__ == "__main__":
    m = Map(21, 21)
    print(m.mapData())
